The present invention relates to database management systems and more particularly to methods and apparatus for implementing indexes in database management systems.
Database management systems provide users the ability to store, update, and retrieve information by submitting commands to a database server. To be correctly processed, the commands must comply with a database language that is supported by the database server. One popular database language is known as the Structured Query Language (SQL). SQL provides a user with the ability to create tables that can be used to store various types of information.
Database management systems typically create tables in the form of abstract data structures and/or objects for retaining information. The tables are generally organized in the form of rows and columns. Each row in the table represents an individual record. For example, a table that stores employee records may contain columns that store: last names, first names, date of birth, employee number, department, etc. Each row in the table stores the same column information for a different employee.
SQL also provides a user with the ability to generate complex queries that can be used to retrieve specific information from the tables. The information retrieved may be further organized into meaningful form for subsequent presentation and/or analysis. For example, a user may generate a query that results in the creation of an answer table containing only the last names and departments of all employees. This information can be subsequently organized by department in order to assess staffing requirements.
In a typical database system, data is stored in a table in an unordered form. As records are entered into the table, they are inserted into the next available location. Such a location can often be at a non-contiguous storage sector of a permanent storage device, such as a fixed disk drive or optical drive, relative to the location of the previous record. Consequently, it is not always possible to directly access and/or retrieve a specific record or a range of records. In the absence of supplemental data structures, every row in the table must be examined to properly execute a query that requires retrieval of one or more records.
Many database systems provide an object type called an index that can significantly increase the speed of certain data retrieval processes. A database index is conceptually similar to a normal index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied by a reference location within the book where the information can be found. The index is maintained separately from the actual database table for which the index is created.
A database index can be considered to be a mini table, where each xe2x80x9crowxe2x80x9d is an index entry that contains a key value and a pointer. The key value of an index entry is a value created from the values in one or more columns of a corresponding row of the table. Those columns are referred to as xe2x80x9ckey columnsxe2x80x9d. The pointer of an index entry points to the location of the row that corresponds to the index entry.
For example, assume that an index is built on the last name (or first name) column of the employee table mentioned above. Each entry in the index would include a key value formed from the last name (or first name) column found in a row of the employee table. Thus, a typically entry of the index would have the form  less than Smith, rowid greater than (or John, rowid), where xe2x80x9cSmithxe2x80x9d (or xe2x80x9cJohnxe2x80x9d) is the key value for the index entry, and rowid is a pointer to the corresponding row of the table which has xe2x80x9cSmithxe2x80x9d in the last name column (or xe2x80x9cJohnxe2x80x9d in the first name column).
Unlike the rows of a table, the entries in the index are maintained in a sorted order. For example, if a table contains a column that stores date information, an index may be created on the date column. The resulting index would contain entries that are sorted in an order (typically chronological) that is based on the dates contained therein. Accordingly, information may be efficiently retrieved for a range of dates based on the sorted order of the index.
In order to improve processing of queries involving multiple column constraints, an index can be created on multiple columns of the table. Such an index would include composite key values in the form of column1.column2, where column1 and column2 are the constraint columns from the table. For example, an index built on a student information table can be created on both a grade_level column and a student_identification column. The index would include a composite key (grade_level. student_identification) that is sorted in ascending order based on the grade_level. In addition, within each grade level, the index would be further sorted in ascending order based on the student_identification of students in each particular grade_level.
There are situations where it may be desirable to create the index such that the grade_level sub_key is sorted in ascending order and, within each grade level, the student_identification sub_key is sorted in descending order. Similarly, a client may want the index created such that the grade_level sub_key is sorted in descending order and the student_identification sub_key is sorted in ascending order.
SQL does not provide the ability to sort an index in descending order. There exist, however, specific database systems that provide extended commands which allow sorting of an index in descending order. For example, some approaches to providing descending-ordered indexes do not actually create indexes with entries that are sorted in descending order. Rather, each xe2x80x9cdescendingxe2x80x9d index is created and sorted in ascending order, but read in reverse to simulate an index sorted in descending order. This ability does not allow sorting of indexes that have composite keys such that a first sub_key is sorted in ascending order, while a second sub_key is sorted in descending order.
Another approach to creating indexes having composite keys stores metadata that indicates whether a sub_key should be sorted in ascending order or descending order. The system then switches between two different comparison functions, based on the metadata, to sort each sub_key. Although this allows a first sub_key to sort in ascending order, while a second sub_key sorts in descending order, it requires code that touches indexes to know which sub_keys sort in ascending order, and which sub_keys sort in descending order. Adding special cases such as this to code takes time, makes the code run slower, introduces bugs, and makes future code maintenance more difficult.
Based on the foregoing, a disadvantage associated with current methods of implementing database indexes is the inability to create an index on multiple columns of a table wherein various sub_keys of the index may be sorted in either ascending and/or descending order without requiring all the code that reads and modifies indexes to treat any sub_key as special.
There is a need for methods and apparatus that allow creation of indexes that include composite keys wherein the sub_keys may be individually sorted in ascending order, descending order, or a combination of ascending and descending order, while allowing all code that reads and manipulates indexes to sort all sub_keys in ascending order.
These and other needs are addressed by the present invention, wherein a database server reverses the sortability of key values in an index that must be sorted in descending order, thereby allowing sorting of multiple sub_keys in any combination of ascending or descending order using only one sort function.
The sortability of a key value refers to the characteristic of the key value that determines the order of a key value relative to other key values. For example, a database server may sort based on a letter-by-letter comparison between key values, or based on a byte-by-byte comparison between key values. In a system where sorting is performed on a letter-by-letter basis, the sortability of a key can normally be reversed by replacing xe2x80x98A""s with xe2x80x98Z""s, xe2x80x98B""s with xe2x80x98Y""s, etc. Furthermore, the sortability of a key value is a property of the key value alone, and not a property of the sort method. In other words, the sortability of a key value dictates the order in which the keys are sorted using a prescribed sort method.
If a first key K1 has a value that is greater than the value of a second key K2, then the second key K2 would precede the first key K1 in the sort order. Under these circumstances, the sortability of K2 is reversed by mapping the value of K2 to a value that is greater than the first key K1. Accordingly, after the sortability of K2 has been reversed relative to K1, K1 would precede the second key K2 in the sort order. The same sort method is used, however, regardless of the sortability of the key values.
In accordance with one aspect of the present invention, a method for implementing descending indexes allows a database server to receive a statement that requires building an index, in descending order, on at least one key column. Next, the sortability of each key value in the key columns is reversed to form a plurality of reversed key values. The database server creates the index and sorts the reversed key values from the key columns in ascending order.
According to another aspect of the invention, the reversal process is selected such that the original key values can be reconstructed from the reversed key values. The index entries are sorted based on their reversed key values, hence resulting in an ordering of the index key values that is reversed (i.e., descending order) relative to the ordering that would have resulted if the index entries had been sorted based on the original key values. After the index entries are sorted, the original key values are reconstructed from the reversed key values to allow access to the original key values by the database server.
In addition, the sortability of each value from a key column may be reversed as the value is retrieved from the table, thereby allowing immediate sorting of entries during initial creation of the index. Since the sub_key values from each key column are separate when retrieved from the table, sub_key values from individual key columns may be selectively reversed, and sorted in either ascending order or descending order, during the creation of indexes built on composite keys. This allows the creation of composite-key indexes that contain, for example, a first sub_key sorted in descending order, a second sub_key sorted in ascending order, and a third sub_key sorted in descending order using the same sort method.